#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;

//he

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> leftMax(height.size(), 0);
        vector<int> rightMax(height.size(), 0);
        leftMax[0] = height[0];
        for (int i = 1; i < height.size(); ++i) {
            leftMax[i] = max(height[i],leftMax[i-1]);
        }
        rightMax[height.size() - 1] = height[height.size() - 1];
        for (int i = height.size() - 2; i >= 0; --i) {
            rightMax[i] = max(height[i], rightMax[i+1]);
        }
        int result = 0;
        for (int i = 0; i < height.size(); ++i) {
            result += min(leftMax[i], rightMax[i]) - height[i];
        }
        return result;

    }
};

//int main() {
//    Solution S;
//    vector<int> nums = { 0,1,0,2,1,0,1,3,2,1,2,1 };
//    cout<<S.trap(nums)<<endl;
//}